package com.solution.stack;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    public String reverseParentheses(String s) {
        Deque<String> stack = new LinkedList<>();
        StringBuffer str = new StringBuffer();
        for ( int i = 0; i < s.length() ; i++ ) {
            char ch = s.charAt(i);
            if ( ch == '(' ) {
                stack.push(str.toString());
                str.setLength(0);
            } else if ( ch == ')' ) {
                str.reverse();
                str.insert(0, stack.pop());
            } else {
                str.append(ch);
            }
        }
        return str.toString();
    }
}
/*
复杂度分析

时间复杂度：O(n^2)，其中 n 为字符串的长度。栈的最大深度为 O(n)，每一层处理的时间复杂度主要为反转的时间复杂度，为 O(n)，因此总时间复杂度为 O(n^2)。

空间复杂度：O(n)，其中 n 为字符串的长度。对于任意时刻，字符串中的任意一个字符至多只被栈中的一个位置包含一次。
 */